//给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 
//
// 题目数据保证答案符合 32 位整数范围。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3], target = 4
//输出：7
//解释：
//所有可能的组合为：
//(1, 1, 1, 1)
//(1, 1, 2)
//(1, 2, 1)
//(1, 3)
//(2, 1, 1)
//(2, 2)
//(3, 1)
//请注意，顺序不同的序列被视作不同的组合。
// 
//
// 示例 2： 
//
// 
//输入：nums = [9], target = 3
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// 1 <= nums[i] <= 1000 
// nums 中的所有元素 互不相同 
// 1 <= target <= 1000 
// 
//
// 
//
// 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？ 
// Related Topics 数组 动态规划 
// 👍 537 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class CombinationSumIv {
    public static void main(String[] args) {
        Solution solution = new CombinationSumIv().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * ！！如果求组合数就是外层for循环遍历物品，内层for遍历背包。
     * 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
     * 本题是求的排列数，所以可以外层遍历背包，内层遍历物品，降低时间复杂度
     *
     * 定睛一看就是一道完全背包的dp的题目
     * 状态定义dp[i][j]为取前i个数，结果为j的情况总和
     * 我先将数组进行了排序，便于写条件
     * 状态转移方程：顺序不同也算不同结果，我自己写的时候dp[i][j]分了三种情况讨论
     * 1.当j<nums[i]的时候，直接是上一行的结果
     * 2.当j = nums[i]的时候，直接是上一行+1
     * 3.当j>nums[i]的时候，先将当前位置归零，再对在本行所有j-nums[k]的累加
     * 所有当前值j-一个硬币剩下值的结果的和
     * 即dp[i][j-nums[i]] + dp[i][j-nums[i-1]] + ... +dp[i][j-nums[0]]
     *
     */
    class Solution {
        public int combinationSum42(int[] nums, int target) {
            if (nums.length == 1) return target%nums[0] == 0 ? 1: 0;
            Arrays.sort(nums);
            int len = nums.length;
            int[][]dp = new int[len][target+1];
            for (int i = nums[0]; i <= target ; i+=nums[0]) {
                dp[0][i] = 1;
            }
            for (int i = 1; i < len ; i++) {
                int num = nums[i];
                for (int j = 0; j <= target ; j++) {
                    if (j<num) dp[i][j] = dp[i-1][j];
                    if (j == num) dp[i][j] = dp[i-1][j]+1;
                    if (j>num){
                        for (int k = 0; k <=i ; k++) {
                            dp[i][j]+=dp[i][j-nums[k]];
                        }
                    }
                }
            }
            return dp[len-1][target];
        }

        /**
         * 压缩空间到一维数组
         */
        public int combinationSum41(int[] nums, int target) {
            if (nums.length == 1) return target%nums[0] == 0 ? 1: 0;
            Arrays.sort(nums);
            int len = nums.length;
            int[]dp = new int[target+1];
            for (int i = nums[0]; i <= target ; i+=nums[0])
                dp[i] = 1;//初始化
            for (int i = 1; i < len ; i++) {
                int num = nums[i];
                if (num>target) break;
                dp[num]++;
                for (int j = num+1; j <= target ; j++) {
                    dp[j] = 0;//这里的dp[j]必须先清零
                    for (int k = 0; k <=i ; k++) {
                        dp[j]+=dp[j-nums[k]];//去掉一个硬币
                    }
                }
            }
            return dp[target];
        }

        /**
         * 最简单的代码
         * 外层遍历背包，内层遍历物品，且压缩空间
         */
        public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target+1];
            dp[0] = 1;//保证单个硬币的合理性
            for (int i = 1; i <=target ; i++) {//外层遍历容量
                for (int num : nums) {//内层遍历价值
                    if (i >= num) dp[i] += dp[i - num];
                }
            }
            return dp[target];
        }

        /**
         * 二刷
         * 没有想起来排列和组合的区别：求排列数外层遍历背包，内层遍历价值（排列方式不同结果不同）
         *                           求组合数外层遍历价值，内层遍历背包（排列方式不同结果相同）
         * 本题目是求的排列数，所以先遍历背包，再遍历物品
         * 注意不同顺序算不同，所以常规dp是不行的，因为常规dp不会统计相同的组合
         * 进行二维推导的时候发现需要遍历之前的所有钱数对应的组合
         * 然后发现只与当前行的值有关，所以直接去掉了一维
         * 我是先遍历的目标值，后遍历的所有钱数，初始化dp[0]=1，这是为了保证单个硬币也算一次
         *
         * 使用dfs也能求解，而且代码很简单，就是时间上复杂很多
         */
        public int combinationSum4two(int[] nums, int target) {
            int len = nums.length;
            Arrays.sort(nums);
            int[] dp = new int[target+1];
            dp[0] = 1;
            for (int j = 1; j<= target; j++){//先遍历容量
                for (int k = 0; k<len && j>=nums[k]; k++)//遍历所有的钱
                    dp[j] += dp[j-nums[k]];//当前值为之前所有的累加和
            }
            return dp[target];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
















